package KwayMergeSort;
// Autumn 2012 TCSS343 Homework 3
// K-Way Mergesort
// YOUR NAME GOES HERE!

import java.util.PriorityQueue;

/**
 * A class that contains a group of sorting algorithms. The input to the sorting
 * algorithms is assumed to be an array of integers.
 * 
 * @author Donald Chinn
 * @author Daniel M. Zimmerman
 * @version October 2012
 */
public final class Sort
{
  /**
   * Reused text constant.
   */
  private static final String FIVE_SPACES = "     ";
  
  /**
   * Reused text constant.
   */
  private static final String BRACKET_EQUALS = "] = ";
  
  /**
   * Private constructor to prevent instantiation.
   */
  private Sort()
  {
    // don't do anything
  }

  /**
   * Given an array of integers and an integer k, sort the array (ascending
   * order) using k-way mergesort.
   * 
   * @param the_data An array of integers.
   * @param the_k The k in k-way mergesort.
   */
  public static void kwayMergesort(final int[] the_data, final int the_k)
  {
    kwayMergesortRecursive(the_data, 0, the_data.length - 1, the_k);
  }

  /**
   * The recursive part of k-way mergesort. Given an array of integers (data), a
   * low index, high index, and an integer k, sort the subarray data[low..high]
   * (ascending order) using k-way mergesort.
   * 
   * @param the_data An array of integers.
   * @param the_low The low index.
   * @param the_high The high index.
   * @param the_k The k in k-way mergesort.
   */
  public static void kwayMergesortRecursive(final int[] the_data, 
                                            final int the_low, final int the_high,
                                            final int the_k)
  {
    if (the_low < the_high)
    {
      for (int i = 0; i < the_k; i++)
      {
        kwayMergesortRecursive(the_data, 
                               the_low + i * (the_high - the_low + 1) / the_k, 
                               the_low + (i + 1) * (the_high - the_low + 1) / the_k - 1,
                               the_k);
      }
      merge(the_data, the_low, the_high, the_k);
    }
  }

  /**
   * Given an array of integers (data), a low index, a high index, and an
   * integer k, sort the subarray data[low..high]. This method assumes that each
   * of the k subarrays data[low + i*(high-low+1)/k .. low + (i+1)*(high-low+1)/k - 1], 
   * for i = 0..k-1, are sorted.
   * 
   * @param the_data An array of integers.
   * @param the_low The low index.
   * @param the_high The high index.
   * @param the_k The k in k-way mergesort.
   */
  public static void merge(final int[] the_data, 
                           final int the_low, final int the_high, 
                           final int the_k)
  {
    if (the_high < the_low + the_k)
    {
      // the subarray has k or fewer elements, 
      // so just make one big heap and do deleteMins on it
      final PriorityQueue<MergesortHeapNode> heap = 
          new PriorityQueue<MergesortHeapNode>();
      for (int j = the_low; j <= the_high; j++)
      {
        heap.add(new MergesortHeapNode(the_data[j], 0));
      }
      for (int j = the_low; j <= the_high; j++)
      {
        try
        {
          the_data[j] = heap.remove().data();
        }
        catch (final IllegalStateException e)
        {
          System.out.println("Tried to delete from an empty heap.");
        }
      }
    }
    else
    {
      // divide the array into k subarrays and do a k-way merge
      // THIS IS WHERE YOUR CODE GOES
    }
  }

  /**
   * Given integer the_size, produce an array of the_size random integers. The
   * integers of the array are between 0 and the_size (inclusive) with random
   * uniform distribution.
   * 
   * @param the_size The number of elements in the returned array.
   * @return an array of the_size randomly generated integers.
   */
  public static int[] getRandomArrayOfIntegers(final int the_size)
  {
    final int[] data = new int[the_size];
    for (int i = 0; i < the_size; i++)
    {
      data[i] = (int) ((the_size + 1) * Math.random());
    }
    return data;
  }

  /**
   * Given an integer the_size, produce an array of the_size random integers. The
   * integers of the output array are between 0 and the_size-1 with exactly one of
   * each in the array. Each permutation is generated with random uniform
   * distribution.
   * 
   * @param the_size The number of elements in the returned array.
   * @return an array of integers.
   */
  public static int[] getRandomPermutationOfIntegers(final int the_size)
  {
    final int[] data = new int[the_size];
    for (int i = 0; i < the_size; i++)
    {
      data[i] = i;
    }
    // shuffle the array
    for (int i = 0; i < the_size; i++)
    {
      int temp;
      final int swap = i + (int) ((the_size - i) * Math.random());
      temp = data[i];
      data[i] = data[swap];
      data[swap] = temp;
    }
    return data;
  }

  /**
   * Perform checks to see if the algorithm has a bug.
   */
  private static void correctnessTest()
  {
    final int[] data = getRandomPermutationOfIntegers(100);

    for (int i = 0; i < data.length; i++)
    {
      System.out.println("data[" + i + BRACKET_EQUALS + data[i]);
    }

    final int k = 1000;
    kwayMergesort(data, k);

    // verify that data[i] = i
    boolean error = false;
    for (int i = 0; i < data.length; i++)
    {
      if (data[i] != i)
      {
        error = true;
        System.out.println("Error!  data[" + i + BRACKET_EQUALS + data[i] + ".");
      }
    }
    if (!error)
    {
      System.out.println("data was correctly sorted");
    }
  }

  /**
   * Perform timing experiments.
   */
  private static void timingTest()
  {
    // start the timer
    final long start_time = System.currentTimeMillis();
    
    final int n = 100000; // n = size of the array
    final int k = 3; // k = k in k-way mergesort
    final int[] data = getRandomArrayOfIntegers(n);
    kwayMergesort(data, k);

    // stop the timer
    final long finish_time = System.currentTimeMillis();
    final long total_time = finish_time - start_time;

    System.out.println("** Results for k-way mergesort:");
    System.out.println(FIVE_SPACES + "n = " + n + FIVE_SPACES + "k = " + k);
    System.out.println(FIVE_SPACES + "Time: " + total_time + " ms.");
  }

  /**
   * Code to test the sorting algorithms.
   * 
   * @param the_args Command line arguments.
   */
  public static void main(final String[] the_args)
  {
    correctnessTest();
    timingTest();
    
    // EITHER ADD CODE HERE TO DO ALL THE RUNS YOU WANT TO DO AND
    // TIME THEM, OR USE A TOOL LIKE JUNIT FOR AUTOMATED TESTS
    
    // YOU MIGHT ALSO WANT TO MODIFY THE timingTest METHOD TO BE
    // MORE USEFUL TO YOU...
  }
}
